// 给定一整数数组 nums ，请设计算法找出数组中乘积最大的连续子数组（至少包含一个数字），
// 并返回该子数组所对应的乘积。

var maxProduct: (nums: number[]) => number | undefined = function (nums) {
    // 边界情况检验
    if (nums.length === 0) {
        return;
    }
    // 定义两个动态规划变量dp，分别存储当前最大值和最小值
    let dpMax: number = nums[0];
    let dpMin: number = nums[0];
    // 定义结果变量并初始化
    let res: number = nums[0];
    for (let i: number = 1; i < nums.length; i++) {
        // 重要：当前元素为负数时最大最小dp值需要交换
        if (nums[i] < 0) {
            let temp: number = dpMax;
            dpMax = dpMin;
            dpMin = temp;
        }
        // 状态转移方程：不断维护max、min的dp值
        dpMax = Math.max(dpMax * nums[i], nums[i]);
        dpMin = Math.min(dpMin * nums[i], nums[i]);
        // 不断维护结果变量
        res = Math.max(res, dpMax);
    }
    return res;
};

        // 首先这道题比较明显还是属于需要使用动态规划算法
        // 而还有一个常用的求解连续子数组问题的滑动窗口算法则需要满足
        // 在使用两个变量同向移动或者相向移动的过程中，一边排除了不必要的区间，但依然不丢失最优解的性质
        // 而这道题显然因为负数的存在，会丢失最优解，所以不能使用滑动窗口算法
        // 首先我们进行状态定义：在这道题中我们定义dp变量为包含当前元素结果乘积最大的子数组
        // 然后遍历数组时计算当前最大值，不断更新dp值
        // 而状态转移方程也比较好找到，就是当前元素乘上一个元素的dp值与当前元素之间比较哪个大？
        // 但在这里有一个深坑，大家需要思考：
        // “由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值dpMin”
        // 所以当负数出现的时候，我们需要将则dpmax与dpmin进行交换再进行下一步计算
        // 最后用一个result变量来不断地更新当前的最大值返回即可。